export const userid = [113107, 113106, 113105, 113104, 113103, 113102, 113101, 113100, 113099, 113098, 113097, 113096, 113095, 113094, 113093, 113092, 113091, 113090, 113089, 113088, 113087, 113086, 113085, 113084, 113083, 113082, 113081, 113080, 113079, 113078, 113077, 113076, 113075, 113074, 113073, 113072, 113071, 113070, 113069, 113068, 113067, 113066, 113065, 113064, 113063, 113062, 113061, 113060, 113059, 113058, 113057]

export const activityid = 100234

export const questionid = [
  110748,
  110747,
  110746,
  110745,
  110744,
  110744,
  110742,
  110741,
  110740,
  110739,
  110738,
  110737,
  110736,
  110735,
  110734,
  110733,
  110732,
  110731,
  110730,
  110729,
  110728,
  110727,
  110726,
  110725,
  110724,
  110723,
  110722,
  110721,
  110720,
  110719,
  110718,
  110717,
  110716,
  110715,
  110714,
  110713,
  110712,
  110711,
  110710,
  110709,
  110708,
  110707,
  110706,
  110705,
  110704,
  110703,
  110702,
  110701,
  110700,
  110699,
  110698,
  110697,
  110696,
  110695,
  110694,
  110693,
  110692,
  110691
]

export const contexts = [
  `#include <stdio.h>

    int main()
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\\n", a+b);
        return 0;
    }
    `,
  `
    #include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int a[105],ls[105],rs[105],kkk[105];//a:lie,ls:left scope,rs:right scope（原谅我的工地英语），kkk是行（kkksc03不要打我[滑稽]）
void print()
{
 if(ans<=2)
 {
 	for(int i=1;i<=n;i++)
 	cout<<kkk[i]<<" ";
 	cout<<endl;
 }//输出前三组解
 ans++;
}
void dfs(int k)//深搜
{
 if(k>n)
 {
 	print();
 	return ;
 }
 for(int i=1;i<=n;i++)
 {
 	if(!a[i]&&!ls[i+k]&&!rs[i-k+n])
 	{
 		kkk[k]=i;
 		a[i]=1;
 		ls[k+i]=1;
 		rs[i-k+n]=1;//以上是“占领”操作
 		dfs(k+1);//这个是深搜下一行
 		a[i]=0;//以下是回溯操作
 		ls[k+i]=0;
 		rs[i-k+n]=0;
 	}
 }
}
int main ()
{
 cin>>n;
 dfs(1);//开始
 cout<<ans<<endl;//结束
 return 0;//大工告成！
}

    `,
  `
    #include<bits/stdc++.h>
#define inl inline
#define reg register

using namespace std;

namespace zzc
{
    inl int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
        return x*f;
    }

    const int maxn = 4e3+5;
    const int mod = 1e8+7;
    int n,m,qt,t,lst,blo,num;
    int bel[maxn],lef[maxn],rig[maxn],q[maxn],w[maxn];
    
    struct node
    {
        int c,v,t;
    }a[maxn];

    struct sqr
    {
        int f[maxn];
        void clear()
        {
            memset(f,0,sizeof(f));
        }
        void insert(node x)
        {
            int lim=min(x.c-1,m-x.c);
            for(reg int i=0;i<=lim;i++)
            {
                int head=1,tail=1;
                q[1]=0;
                w[0]=f[i];
                for(reg int j=1,cst=x.c+i;cst<=m;cst+=x.c,j++)
                {
                    w[j]=f[cst]-j*x.v;
                    while(head<=tail&&j-q[head]>x.t) head++;
                    while(head<=tail&&w[q[tail]]<w[j]) tail--;
                    q[++tail]=j;
                    f[cst]=w[q[head]]+j*x.v;
                }
            }
        }
    }b[45][45],ans;
    
    void solve()
    {
        int l,r;
        n=read();m=read();qt=read();lst=0;
        for(reg int i=1;i<=n;i++) a[i].c=read();
        for(reg int i=1;i<=n;i++) a[i].v=read();
        for(reg int i=1;i<=n;i++) a[i].t=read();
        blo=sqrt(n);num=n/blo;
        if(n%blo) num++;
        for(reg int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
        for(reg int i=1;i<=num;i++)
        {
            lef[i]=(i-1)*blo+1;
            rig[i]=min(n,i*blo);
        }
        lef[num+1]=n+1;
        for(reg int i=0;i<num;i++)
        {
            b[i][num+1].clear();
            for(reg int j=1;j<=rig[i];j++) b[i][num+1].insert(a[j]);
            for(reg int j=num;j>i;j--)
            {
                b[i][j]=b[i][j+1];
                for(reg int k=lef[j];k<lef[j+1];k++) b[i][j].insert(a[k]);
            }
        }
        while(qt--)
        {
            l=(read()+lst-1)%n+1;
            r=(read()+lst-1)%n+1;
            if(l>r) swap(l,r);
            ans=b[bel[l]-1][bel[r]+1];
            for(reg int i=lef[bel[l]];i<l;i++) ans.insert(a[i]);
            for(reg int i=r+1;i<=rig[bel[r]];i++) ans.insert(a[i]);
            lst=0;int res=0;
            for(reg int i=1;i<=m;i++) 
            {
                lst=(lst+ans.f[i])%mod;
                res^=ans.f[i];
            }
            printf("%d %d\\n",lst,res);
        }
    }

    void work()
    {
        t=read();
        while(t--) solve();
    }
}

int main()
{
//	freopen("4.in","r",stdin);
//	freopen("4.out","w",stdout);
    zzc::work();
    return 0;
}

    `,
  `
    #include <iostream>

using namespace std;
const int N = 2e6+10;

int f[N],d[N];
int ans = 0x3f3f3f3f;

int find(int x){
    if(x == f[x])
        return x;
    int t = f[x];
    f[x] = find(f[x]);
    d[x] += d[t];
    return f[x];
}

void unoin(int l,int r){
    int x = find(l),y = find(r);
    if(x == y)
        ans = min(ans,d[l] + d[r] + 1);
    else{
        f[x] = y;
        d[l] = d[r] + 1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++)
        f[i] = i;
    for(int i = 1;i <= n;i ++){
        int x;
        cin >> x;
        unoin(i,x);
    }
    cout << ans << endl;

    return 0;
}

    `,
  `
    #include <bits/stdc++.h>

namespace IO {
  const int IN_LEN = 1 << 18 | 1;
  static char buf[IN_LEN] , *s , *t;
  inline int Getchar( void ) { return s == t && ( t = ( s = buf ) + fread( buf , 1 , IN_LEN , stdin ) ) , s == t ? -1 : *s++; }
  template <class T> inline void read( T & x ) {
    static int c , f; c = Getchar() , x = f = 0;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = 1; c = Getchar(); }
    while( c <= '9' && c >= '0' ) x = x * 10 + c - 48 , c = Getchar();
    x = f ? -x : x;
  }
} using IO::read;

using namespace std;

typedef long long lol;
typedef pair<int,int> pii;
const int N = 5e3 + 5;
const int M = 1e7 + 5;
const int V = 15;
const int mod = 998244353;
const int inv2 = ( mod + 1 ) / 2;
const int base1 = 131 , base2 = 1145141 , base3 = 1926;
inline int pls( int a , int b ) { a += b - mod; return a + ( a >> 31 & mod ); }
inline int mns( int a , int b ) { a -= b; return a + ( a >> 31 & mod ); } 
inline void inc( int & a , int b ) { a += b - mod; a += a >> 31 & mod; }
inline void dec( int & a , int b ) { a -= b; a += a >> 31 & mod; }
inline int fpow( int b , int k ) {
  int res = 1;
  while( k ) {
    if( k & 1 ) res = 1LL * res * b % mod; 
    b = 1LL * b * b % mod; k >>= 1;
  } return res;
} 

int n , k , d[M] , S[M] , ans , binom[N][V] , fac[V] , ifac[V] , inv[V];
inline void initdeg( int n ) { for( int i = 0 ; i <= n ; ++i ) d[i] = S[i] = 0; }

struct Graph {
  int head[M] , eidx , n;
  struct Edge { int nxt , to; } edge[M];
  Graph() { eidx = 1; }
  inline void init( int _n ) { n = _n; memset( head + 1 , 0 , sizeof( int ) * n ); eidx = 1; }
  inline void addedge( int u , int v ) {
    edge[++eidx] = (Edge) { head[u] , v }; head[u] = eidx;
    edge[++eidx] = (Edge) { head[v] , u }; head[v] = eidx;
  }
  int calc1( void ) { return eidx / 2; }
  int calc2( void ) { 
    initdeg( n ); int res = 0;
    for( int e = 2 ; e <= eidx ; ++e ) ++d[edge[e].to];
    for( int i = 1 ; i <= n ; ++i ) inc( res , 1LL * d[i] * ( d[i] - 1 ) % mod );
    return 1LL * res * inv2 % mod;
  }
  int calc3( void ) {
    initdeg( n ); int res = 0;
    for( int e = 2 ; e <= eidx ; ++e ) ++d[edge[e].to];
    for( int e = 2 ; e <= eidx ; e +=2 ) inc( res , 1LL * ( d[edge[e].to] - 1 ) * ( d[edge[e ^ 1].to] - 1 ) % mod );
    for( int i = 1 ; i <= n ; ++i ) inc( res , 1LL * d[i] * ( d[i] - 1 ) % mod * ( d[i] - 2 ) % mod * inv2 % mod );
    return res;
  }
  int calc4( void ) {
    initdeg( n ); int res = 0;
    for( int e = 2 ; e <= eidx ; ++e ) ++d[edge[e].to];
    for( int e = 2 , tmp ; e <= eidx ; e += 2 ) {
      tmp = d[edge[e].to] + d[edge[e ^ 1].to] - 3;
      dec( res , 1LL * tmp * tmp % mod );
      S[edge[e].to] += tmp;
      S[edge[e ^ 1].to] += tmp;
      ++tmp; inc( res , ( 1LL * tmp * ( tmp - 1 ) * ( tmp - 2 ) / 2 ) % mod );
    }
    for( int i = 1 ; i <= n ; ++i ) inc( res , 1LL * inv2 * S[i] % mod * S[i] % mod );
    return res;
  }
  void generate( Graph & res ) {
    res.init( ( eidx / 2 ) );
    for( int e = 2 , u ; e <= eidx ; ++e ) {
      u = edge[e].to;
      for( int i = head[u] ; i ; i = edge[i].nxt )
        if( ( e >> 1 ) < ( i >> 1 ) )
          res.addedge( e >> 1 , i >> 1 );
    }
  }
} T , K[2];

map<int,int> HashTable;
int Log[1 << V] , bitcnt[1 << V];

struct Tree {
  int G[V] , fa[V] , hs[V] , HS , siz[V] , n , mark[V] , _siz[V] , f[N][V] , g[1 << V] , leaf[V] , C[V] , leafNum[V];
  void dfs( int u , int p ) {
    int son = 0;
    for( int i = 0 ; i < n ; ++i ) f[u][i] = 0;
    for( int i = T.head[u] , v ; i ; i = T.edge[i].nxt )
      if( ( v = T.edge[i].to ) != p ) dfs( v , u ) , ++son;
    for( int i = 0 ; i < n ; ++i ) if( !leaf[i] && son >= bitcnt[G[i]] ) {
      for( int t = G[i] ; t ; t = (t-1)&G[i] ) {  g[t] = 0; } g[0] = 1;
      for( int j = T.head[u] , v ; j ; j = T.edge[j].nxt )
        if( ( v = T.edge[j].to ) != p ) {
          for( int k = G[i] ; k ; k = (k-1)&G[i] )
            for( int t = k ; t ; t ^= (t&(-t)) )
              inc( g[k] , 1LL * g[k ^ (t&(-t))] * f[v][Log[t&(-t)]] % mod );
        }
      f[u][i] = 1LL * g[G[i]] * binom[son - bitcnt[G[i]]][leafNum[i]] % mod * fac[leafNum[i]] % mod * C[i] % mod;
    }
  }
  int getTimes( void ) {
    for( int i = 0 ; i < n ; ++i )
      leaf[i] = !G[i];
    for( int i = 0 ; i < n ; ++i ) {
      leafNum[i] = 0;
      for( int j = 0 ; j < n ; ++j )
        if( ( G[i] >> j ) & 1 ) {
          leafNum[i] += leaf[j];
          if( leaf[j] ) 
            G[i] ^= ( 1 << j );
        }
    }
    dfs( 1 , 1 );
    int res = 0;
    for( int i = 1 ; i <= ::n ; ++i )
      inc( res , f[i][0] );
    return res;
  }
  void getHash( int u , int type ) {
    static int tmp[V] , tot;
    if( mark[u] ) return;
    if( type ) C[u] = 1;
    siz[u] = 1;
    for( int ts = G[u] , v ; ts ; ts ^= (ts&(-ts)) ) { v = Log[ts&(-ts)]; getHash( v , type ); siz[u] += siz[v]; }
    tot = 0; for( int ts = G[u] , v ; ts ; ts ^= (ts&(-ts)) ) { v = Log[ts&(-ts)]; tmp[++tot] = hs[v]; }
    sort( tmp + 1 , tmp + 1 + tot );
    if( type )
      for( int i = 1 , r ; i <= tot ; i = r + 1 ) {
        r = i; while( r < tot && tmp[r + 1] == tmp[i] ) ++r;
        C[u] = 1LL * C[u] * ifac[r - i + 1] % mod;
      }
    for( int i = 1 ; i <= tot ; ++i ) hs[u] = ( 1LL * hs[u] * base1 + tmp[i] ) % mod;
    hs[u] = ( ( 1LL * hs[u] * base2 + siz[u] ) % mod * base3 + 19491001 ) % mod;
  }
  int judge( int s ) {
    for( int i = 0 ; i < n ; ++i ) { _siz[i] = siz[i] , hs[i] = mark[i] = 0; siz[i] = 0; }
    int rt = -1; for( int i = 0 ; i < n ; ++i )
      if( ( s >> i ) & 1 ) {
        if( !~rt || _siz[i] > _siz[rt] ) rt = i;
      } else mark[i] = 1; 
    getHash( rt , 0 );
    int flag = 0;
    for( int i = 0 ; i < n ; ++i ) {
      if( ( ( s >> i ) & 1 ) && !siz[i] ) flag = 1;
      siz[i] = _siz[i];
    } 
    if( !HashTable.count( hs[rt] ) ) flag = 1;
    return flag ? -1 : hs[rt];
  }
  int getValue( void ) {
    K[0].init( n );
    for( int i = 0 ; i < n ; ++i )
      for( int j = 0 ; j < n ; ++j )
        if( ( G[i] >> j ) & 1 )
          K[0].addedge( i + 1 , j + 1 );
    for( int i = 1 ; i <= k - 4 ; ++i )
      K[(i&1)^1].generate( K[i&1] );
    int res = K[(k-4)&1].calc4();
    for( int i = ( 1 << n ) - 2 , subhs ; i ; --i )
      if( ~( subhs = judge( i ) ) )
        dec( res , HashTable[subhs] );
    return res;
  }
  void generate( int * stk , int _n ) {
    n = _n; int now = 0 , idx = 0;
    for( int i = 0 ; i < n ; ++i ) G[i] = fa[i] = hs[i] = siz[i] = mark[i] = 0;
    for( int i = 1 ; i <= n * 2 - 2 ; ++i )
      if( stk[i] > 0 ) fa[++idx] = now , G[now] |= ( 1 << idx ) , now = idx;
      else now = fa[now];
    getHash( 0 , 1 );
    HS = hs[0];
  }
} tree;

int stk[N];

void getTree( int u , int tp , int tot , int lim ) {
  if( u == ( lim * 2 ) - 1 ) {
    tree.generate( stk , lim );
    if( HashTable.count( tree.HS ) ) return;
    HashTable[tree.HS] = tree.getValue();
    inc( ans , 1LL * HashTable[tree.HS] * tree.getTimes() % mod );
    return;
  }
  if( tp ) stk[u] = -1 , getTree( u + 1 , tp - 1 , tot , lim );
  if( tot < lim - 1 ) stk[u] = 1 , getTree( u + 1 , tp + 1 , tot + 1 , lim );
}

int main( void ) {
  read( n ) , read( k ); T.init( n );
  for( int i = 1 , u , v ; i < n ; ++i ) {
    read( u ) , read( v );
    T.addedge( u , v );
  } 
  if( k == 1 ) return printf("%d",T.calc1()),0;
  if( k == 2 ) return printf("%d",T.calc2()),0;
  if( k == 3 ) return printf("%d",T.calc3()),0;
  if( k == 4 ) return printf("%d",T.calc4()),0;
  ifac[0] = ifac[1] = fac[0] = fac[1] = inv[1] = 1 , bitcnt[1] = 1;
  for( int i = 2 ; i < V ; ++i ) {
    fac[i] = 1LL * fac[i - 1] * i % mod;
    inv[i] = 1LL * ( mod - mod / i ) * inv[mod % i] % mod;
    ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
  }
  for( int i = 0 ; i < N ; ++i ) {
    binom[i][0] = 1; for( int j = 1 , t = min( V - 1 , i ) ; j <= t ; ++j )
      binom[i][j] = pls( binom[i - 1][j - 1] , binom[i - 1][j] );
  }
  for( int i = 2 ; i < ( 1 << V ) ; ++i ) Log[i] = Log[i >> 1] + 1 , bitcnt[i] = bitcnt[i >> 1] + (i&1);
  for( int i = 1 ; i <= k + 1 ; ++i ) getTree( 1 , 0 , 0 , i );
  printf("%d\\n",ans);
  return 0;
}

    `,
  `
    #include <bits/stdc++.h>
using namespace std;
#define ll long long

int m, cnt, tot;
char s[1000];
ll prime[500000], p[500000], num[500000];
ll M[25] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 61};

inline ll read() {
	ll x = 0; char c = getchar(); bool f = 1;
	while(c < '0' || c > '9') { if(c == '-') f = !f; c = getchar(); }
	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	return f ? x : -x;
}
ll ksc(ll x, ll y, ll p) {
	ll z = (long double) x / p * y;
	ll res = (unsigned ll) x * y - z * p;
	return (res + p) % p;
}
ll ksm(ll x, ll y, ll p) {
	ll r = 1;
	for(; y; y >>= 1, x = ksc(x, x, p)) 
		if(y & 1) r = ksc(r, x, p);
	return r % p;
}
bool Miller_Rabin(ll n) {
	if(n < 3) return n == 2;
	ll a = n - 1, b = 0;
	while(a % 2 == 0) a /= 2, b++;
	for(int i = 1; i <= 11; i++) {
		if(M[i] == n) return 1;
		ll v = M[i];
		v = ksm(v, a, n);
		if(v == 1 || v == n - 1) continue;
		int j;
		for(j = 1; j <= b; j++) {
			v = ksc(v, v, n);
			if(v == n - 1) break;
		}
		if(j > b) return 0;
	}
	return 1;
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll f(ll x, ll c, ll n) { return (ksc(x, x, n) + c) % n; }
ll Pollard_Rho(ll x) {
	ll c = rand() % (x - 1) + 1;
	ll val = 1;
	ll s = 0, t = 0;
	for(int goal = 1; ; goal <<= 1, s = t, val = 1) {
		for(int step = 1; step <= goal; step++) {
			t = f(t, c, x);
			val = ksc(val, abs(t - s), x);
			if(step % 127 == 0) {
				ll d = gcd(val, x);
				if(d > 1) return d;
			}
		}
		ll d = gcd(val, x);
		if(d > 1) return d;
	}
}
void fac(ll x) {
	if(x < 2) return;
	if(Miller_Rabin(x)) { cnt++, p[cnt] = prime[cnt] = x; return; }
	ll p = Pollard_Rho(x);
	while(p >= x) p = Pollard_Rho(x);
	fac(p);
	fac(x / p);
}
void gjd() {
	int len = strlen(s + 1);
    reverse(s + 1, s + 1 + len);
    int add = 0;
    for(int i = 1 ; i <= len ; i ++) {
        int x = s[i] - '0';
        x *= 2;
        x += add; add = 0;
        if(x >= 10) add = 1, x %= 10;
        s[i] = x + '0';
    }
    if(add != 0) s[++ len] = '1';
    reverse(s + 1, s + 1 + len);
}
bool cmp(ll a, ll b) { return a > b; }
int main() {
	// freopen("a.in", "r", stdin);
	// freopen("a.out", "w", stdout);

	srand((unsigned) time(NULL));
	m = read();
	for(int i = 1; i <= m; i++) fac(read());
	sort(p + 1, p + 1 + cnt);
	sort(prime + 1, prime + 1 + cnt);
	ll q = unique(p + 1, p + 1 + cnt) - p - 1;
	for(int i = 1; i <= cnt; i++) {
		ll pos = lower_bound(p + 1, p + 1 + q, prime[i]) - p;
		num[pos]++;
	}
	// for(int i = 1; i <= cnt; i++) if(prime[i] != prime[i - 1])cout << prime[i] << ' '; cout << endl;
	// for(int i = 1; i <= q; i++) cout << num[i] << ' '; cout << endl;
	ll ans = 1;
	sort(num + 1, num + q + 1, cmp);
	for(int i = 2; i <= q; i++) 
		if(num[i] == num[1]) ans++;
		else break;
	// cout << ans << endl;
	printf("%lld\\n", num[1]);
	s[1] = '1';
	while(ans--) gjd();
	int len = strlen(s + 1); 
	int x = s[len]; x--; s[len] = char(x); 
	for(int i = 1; i <= len; i++) cout << s[i];
	return 0;
}

    `,
  `
    #include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define rep2(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}	
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\\n');
}
template<typename T> void chkmax(T &x,T y){x=x>y?x:y;}
struct wzy{
	int nxt,vertice;
}edge[200010];
int head[100010];int len=0;
void jb(int x,int y){
	edge[++len].nxt=head[x];edge[len].vertice=y;head[x]=len;
	return;
}
struct node{
	long long val;
	node *nxt;
};
node *fH[100010];node *fL[100010];
node *gH[100010];node *gL[100010];

int n;int dep[100010];int L[100010];int Lson[100010];
int d[100010];int col=0;
void Pretreatment(int u,int fr){
	dep[u]=dep[fr]+1;L[u]=0;
	d[++col]=u;Lson[u]=0;
	for(int i=head[u];i;i=edge[i].nxt){
		int nop=edge[i].vertice;
		if(nop==fr)continue;
		Pretreatment(nop,u);
		if(L[nop]+1>L[u]){L[u]=L[nop]+1;Lson[u]=nop;}
	}
	return;
}

int main(){
	read(n);
	rep(i,1,n-1){
		int x,y;read(x);read(y);
		jb(x,y);jb(y,x);
	}
	Pretreatment(1,0);
	
	long long ans=0;
	rep2(s,n,1){
		int x=d[s];
		if(!Lson[x]){
			fH[x]=new node;fH[x]->val=1;fL[x]=fH[x];
			gH[x]=new node;gH[x]->val=0;gL[x]=gH[x];
		}else{
			node *p1,*p2,*p3;
			node *p=gH[Lson[x]];p=p->nxt;
			if(p!=NULL)ans+=p->val;
			fH[x]=fH[Lson[x]];fL[x]=fL[Lson[x]];gH[x]=gH[Lson[x]];gL[x]=gL[Lson[x]];
			p=new node;p->nxt=fH[x];fH[x]=p;p->val=1;
			p=new node;gL[x]->nxt=p;gL[x]=p;p->val=0;
			p=new node;gL[x]->nxt=p;gL[x]=p;p->val=0;
			p=gH[x];gH[x]=p->nxt;free(p);
			
			for(int i=head[x];i;i=edge[i].nxt){
				int nop=edge[i].vertice;
				if(dep[nop]<dep[x]||nop==Lson[x])continue;
				p1=fH[nop];p2=gH[x];p2=p2->nxt;
				rep(j,0,L[nop]){ans+=1ll*p1->val*p2->val;p1=p1->nxt;p2=p2->nxt;}
				p1=gH[nop];p1=p1->nxt;p2=fH[x];
				rep(j,1,L[nop]){ans+=1ll*p1->val*p2->val;p1=p1->nxt;p2=p2->nxt;}
				p1=gH[x];p1=p1->nxt;p2=fH[x];p2=p2->nxt;p3=fH[nop];
				rep(j,1,L[nop]+1){p1->val+=1ll*p2->val*p3->val;p1=p1->nxt;p2=p2->nxt;p3=p3->nxt;}
				p1=gH[x];p2=gH[nop];p2=p2->nxt;
				rep(j,0,L[nop]-1){p1->val+=p2->val;p1=p1->nxt;p2=p2->nxt;}
				p1=fH[x];p1=p1->nxt;p2=fH[nop];
				rep(j,1,L[nop]+1){p1->val+=p2->val;p1=p1->nxt;p2=p2->nxt;}
			}
			/*ans+=g[id[Lson[x]]][1];
			f[id[x]].push_front(1);g[id[x]].pop_front();g[id[x]].push_back(0);
			for(int i=head[x];i;i=edge[i].nxt){
				int nop=edge[i].vertice;
				if(dep[nop]<dep[x]||nop==Lson[x])continue;
				rep(j,0,L[nop])ans+=1ll*f[id[nop]][j]*g[id[x]][j+1];
				rep(j,1,L[nop])ans+=1ll*g[id[nop]][j]*f[id[x]][j-1];
				rep(j,1,L[nop]+1)g[id[x]][j]+=1ll*f[id[x]][j]*f[id[nop]][j-1];
				rep(j,0,L[nop]-1)g[id[x]][j]+=g[id[nop]][j+1];
				rep(j,1,L[nop]+1)f[id[x]][j]+=f[id[nop]][j-1];
			}*/
		}
	}
	write(ans);
	return 0;
}

    `

]